package cn.initcap.algorithm.sort.heap;

import cn.initcap.algorithm.sort.SortTestHelper;

/**
 * 不使用一个额外的最大堆, 直接在原数组上进行原地的堆排序 O(nlogn)级别
 *
 * @author initcap
 * @date Created in 2018/6/21 PM5:19.
 */
public class HeapSort {

    private HeapSort() {
    }

    public static void sort(Comparable[] arr) {

        int n = arr.length;

        // 注意，此时我们的堆是从0开始索引的
        // 从(最后一个元素的索引-1)/2开始
        // 最后一个元素的索引 = n-1
        for (int i = (n - 1 - 1) >> 1; i >= 0; i--) {
            shiftDown2(arr, n, i);
        }
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            shiftDown2(arr, i, 0);
        }
    }

    /**
     * 交换堆中索引为i和j的两个元素
     *
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    /**
     * 原始的shiftDown过程
     *
     * @param arr
     * @param n
     * @param k
     */
    private static void shiftDown(Comparable[] arr, int n, int k) {

        while (k << 1 + 1 < n) {
            int j = k << 1 + 1;
            if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) {
                j += 1;
            }
            if (arr[k].compareTo(arr[j]) >= 0) {
                break;
            }

            swap(arr, k, j);
            k = j;
        }
    }

    /**
     * 优化的shiftDown过程, 使用赋值的方式取代不断的swap,
     * 该优化思想和我们之前对插入排序进行优化的思路是一致的
     *
     * @param arr
     * @param n
     * @param k
     */
    private static void shiftDown2(Comparable[] arr, int n, int k) {

        Comparable e = arr[k];
        while (k << 1 + 1 < n) {
            int j = k << 1 + 1;
            if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) {
                j += 1;
            }
            if (e.compareTo(arr[j]) >= 0) {
                break;
            }
            arr[k] = arr[j];
            k = j;
        }

        arr[k] = e;
    }

    public static void main(String[] args) {

        int n = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(n, 0, 100000);
        SortTestHelper.testSort("cn.initcap.algorithm.sort.heap.HeapSort", arr);

        return;
    }

}
